#ifndef TAGSOLUTION_H_INCLUDED
#define TAGSOLUTION_H_INCLUDED
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

class TagSolution
{
public:
    // позиции храним в виде целого числа
    // когда нужно, для удобства переводим в вектор
    TagSolution(int i)
    : currentPosition(i) {}

    bool solutionExists(int position);
    void getSolution();

private:

    vector<int> convertPositionToVector(int position) const;
    int getHeuristic(int position) const;
    int moveCell(int x1, int y1, int x2, int y2, int position) const;
    vector <int> getNeighbours(int position) const;
    vector<int> getPath(int position);
    vector<int> aStarAlgorithm(int startPosition);
    void printFinalPath(vector<int> path) const;

    const static int destination = 123456780; // конечная позиция

    int currentPosition; // текущая позиция
	set<int> closedPositions; // обработанные позиции
	set<int> openedPositions; // позиции, которые нужно обработать
	set<pair<int, int>> priorityQueue; // очередь с приоритетом для открытых позиций
	map<int, int> parents; // "родители" позиций
	map<int, int> pathCost; // стоимость пути от начальной позиции до данной
	map<int, int> heuristicCost; // эвристическая оценка расстояния до цели
};

// проверяем существование решения игры
// алгоритм взят с e-maxx.ru
bool TagSolution::solutionExists(int position)
{
    vector<int> positionVector = convertPositionToVector(position);
    int numberOfInversions = 0, blankIndex = 0;

    for (int i = 0; i < 9; ++i)
    {
        if (positionVector[i] == 0)
        {
            blankIndex = i;
            break;
        }
    }

    for (int i = 0; i < 9; ++i)
    {
        if (i != blankIndex)
        {
            for (int j = i + 1; j < 9; ++j)
            {
                if ((j != blankIndex) && (positionVector[i] > positionVector[j]))
                {
                    numberOfInversions++;
                }
            }
        }
    }
    return (numberOfInversions % 2 == 0);
}

// переводит позицию поля из целого числа в более удобный вектор
vector<int> TagSolution::convertPositionToVector(int position) const
{
    vector<int> result(9);

    for (int i = 8; i >= 0; --i)
    {
        result[i] = position % 10;
        position /= 10;
    }

    return result;
}

// вычисляет эвристику, используется Манхэттенское расстояние
int TagSolution::getHeuristic(int position) const
{
    int h = 0;
    vector<int> positionVector = convertPositionToVector(position);

    for (int i = 0; i < 9; i++)
    {
        int x = i / 3;
        int y = i % 3;

        if (positionVector[i] != 0)
        {
            h += abs(x - ((positionVector[i] - 1) / 3)) + abs(y - ((positionVector[i] - 1) % 3));
        }
        else
        {
            h += abs(x - 2) + abs(y - 2);
        }
    }

    return h;
}

// меняет в позиции местами клетки с координатами (x1, y1), (x2, y2)
int TagSolution::moveCell(int x1, int y1, int x2, int y2, int position) const
{
	vector<int> resultVector = convertPositionToVector(position);
	int result = 0;

	swap(resultVector[x1 * 3 + y1], resultVector[x2 * 3 + y2]);

	for (int i = 0; i < 9; ++i)
    {
		result *= 10;
		result += resultVector[i];
	}

	return result;
}

// получает "соседей" позиции, т.е. те позиции,
//в которые можно добраться, переместив одну клетку
vector <int> TagSolution::getNeighbours(int position) const
{
	int x = 0, y = 0;
	int pos = position;
	vector<int> result;

	for (int i = 8; i >= 0; --i)
    {
		if (pos % 10 == 0) // ищем пустую клетку
		{
			x = i / 3;
			y = i % 3;
			break;
		}
		pos /= 10;
	}

	if (x != 0)
    {
		result.push_back(moveCell(x, y, x - 1, y, position));
	}
	if (x != 2)
	{
		result.push_back(moveCell(x, y, x + 1, y, position));
	}
	if (y != 0)
	{
		result.push_back(moveCell(x, y, x, y - 1, position));
	}
	if (y != 2)
	{
		result.push_back(moveCell(x, y, x, y + 1, position));
	}
	return result;
}

// возвращает кратчайший путь, переводящий начальную позицию в данную
vector<int> TagSolution::getPath(int position)
{
	vector<int> result;
	// от данной вершины до ее родителя и т.д.
	while((parents.find(position) != parents.end()) && (parents[position] != position))
	{
		result.push_back(position);
		position = parents[position];
	}
	result.push_back(position);

    // переворачиваем вектор
	reverse(result.begin(), result.end());

	return result;
}


// реализация A*
vector<int> TagSolution::aStarAlgorithm(int startPosition)
{
	pathCost[startPosition] = 0;
	heuristicCost[startPosition] = getHeuristic(startPosition);
	openedPositions.insert(startPosition);
	priorityQueue.insert(make_pair(heuristicCost[startPosition], startPosition));


	// пока есть необработанные позиции
	while (!openedPositions.empty())
    {
		// берем вершину с наилучшей эвристикой
		currentPosition = (*priorityQueue.begin()).second;
		if (currentPosition == destination)
        {
			//дошли до завершающей позиции -
			// восстановим путь
			return getPath(currentPosition);
		}
		// удаляем ее из необработанных
		openedPositions.erase(currentPosition);
		// и из очереди
		priorityQueue.erase(priorityQueue.begin());
		// добавляем в обработанные
		closedPositions.insert(currentPosition);

		// обрабатываем всех ее соседей
		vector<int> neighbours = getNeighbours(currentPosition);
		for (int i = 0; i < neighbours.size(); ++i)
        {
			int neighbour = neighbours[i];

			if (closedPositions.find(neighbour) != closedPositions.end())
            {
				// этот сосед уже был обработан
				continue;
			}
			// цена прохождения до этого соседа
			int newCost = pathCost[currentPosition] + 1;
			bool isBetter = false;
			// смотрим, лучше ли этот путь
			if (openedPositions.find(neighbour) == openedPositions.end())
            {
				// сосед не был обработан,
				// надо обработать его и проверить
				isBetter = true;
			}
			else
			{
				// сосед был обработан
				// и возможно старый путь был дороже
				if (newCost < pathCost[neighbour])
				{
					isBetter = true;
				}
			}
			// обновляем информацию
			if (isBetter)
            {
				int newHeuristicCost = newCost + getHeuristic(neighbour);
				parents[neighbour] = currentPosition;
				pathCost[neighbour] = newCost;
				heuristicCost[neighbour] = newHeuristicCost;
				openedPositions.insert(neighbour);
				priorityQueue.insert(make_pair(newHeuristicCost, neighbour));
			}
		}
	}
}

// выводит последовательность движений пустой клетки,
// приводящих ее из начального положения в конечное
void TagSolution::printFinalPath(vector<int> path) const
{
	for (int i = 0; i < path.size() - 1; ++i)
    {
		int from = path[i];
		int to = path[i + 1];
		int fromX = 0, toX = 0, fromY = 0, toY = 0;

		for (int j = 8; j >= 0; --j)
		{
			if (from % 10 == 0)
			{
				fromX = j / 3;
				fromY = j % 3;
			}
			if (to % 10 == 0)
			{
				toX = j / 3;
				toY = j % 3;
			}
			from /= 10;
			to /= 10;
		}

		if ((toX == fromX - 1) && (toY == fromY))
		{
			cout << "u";
		}

		if ((toX == fromX + 1) && (toY == fromY))
		{
			cout << "d";
		}

        if ((toX == fromX) && (toY == fromY - 1))
		{
			cout << "l";
		}

		if ((toX == fromX) && (toY == fromY + 1))
		{
			cout << "r";
		}

	}
}

void TagSolution::getSolution()
{
    // если решения не существует
    if (!solutionExists(currentPosition))
    {
        cout << "No\n";
    }
    else // иначе
    {
        cout << "Yes\n";
        // находим путь до цели
        vector<int> finalPath = aStarAlgorithm(currentPosition);
        // выводим его длину
        cout << finalPath.size() - 1 << endl;
        // и его самого
        printFinalPath(finalPath);
    }
}

#endif // TAGSOLUTION_H_INCLUDED
